SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Algorithmic efficiency</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Algorithmic efficiency</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Program_optimization" title="Program optimization">program optimization</a>, <a href="Optimizing_compiler" title="Optimizing compiler">optimizing compiler</a>, <a href="Loop_optimization" title="Loop optimization">loop optimization</a>, <a href="Object_code_optimizer" title="Object code optimizer">object code optimizer</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1248332772">

/* start https://en.wikipedia.org/ */

.mw-parser-output .multiple-issues-text{width:95%;margin:0.2em 0}.mw-parser-output .multiple-issues-text>.mw-collapsible-content{margin-top:0.3em}.mw-parser-output .compact-ambox .ambox{border:none;border-collapse:collapse;background-color:transparent;margin:0 0 0 1.6em!important;padding:0!important;width:auto;display:block}body.mediawiki .mw-parser-output .compact-ambox .ambox.mbox-small-left{font-size:100%;width:auto;margin:0}.mw-parser-output .compact-ambox .ambox .mbox-text{padding:0!important;margin:0!important}.mw-parser-output .compact-ambox .ambox .mbox-text-span{display:list-item;line-height:1.5em;list-style-type:disc}body.skin-minerva .mw-parser-output .multiple-issues-text>.mw-collapsible-toggle,.mw-parser-output .compact-ambox .ambox .mbox-image,.mw-parser-output .compact-ambox .ambox .mbox-imageright,.mw-parser-output .compact-ambox .ambox .mbox-empty-cell,.mw-parser-output .compact-ambox .hide-when-compact{display:none}

/* end https://en.wikipedia.org/ */

</style>

<p>

In <a href="Computer_science" title="Computer science">computer science</a>, <b>algorithmic efficiency</b> is a property of an <a href="Algorithm" title="Algorithm">algorithm</a> which relates to the amount of <a href="Computational_resource" title="Computational resource">computational resources</a> used by the algorithm. Algorithmic efficiency can be thought of as analogous to engineering <a href="Productivity" title="Productivity">productivity</a> for a repeating or continuous process.

</p><p>For maximum efficiency it is desirable to minimize resource usage. However, different resources such as <a href="Time_complexity" title="Time complexity">time</a> and <a href="Space_complexity" title="Space complexity">space</a> complexity cannot be compared directly, so which of two algorithms is considered to be more efficient often depends on which measure of efficiency is considered most important.

</p><p>For example, <a href="Cycle_sort" title="Cycle sort">cycle sort</a> and <a href="Timsort" title="Timsort">timsort</a> are both <a href="Sorting_algorithm" title="Sorting algorithm">algorithms to sort a list</a> of items from smallest to largest. Cycle sort organizes the list in time proportional to the number of elements squared (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O(n^{2})}</annotation>

</semantics>

</math></span><img src="./5982eaab0c0dfc3f9f0bd9380db63a9e0f6da999.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.009ex;" alt="{\textstyle O(n^{2})}" loading="lazy"></span>, see <a href="Big_O_notation" title="Big O notation">Big O notation</a>), but minimizes the writes to the original array and only requires a small amount of extra <a href="Computer_memory" title="Computer memory">memory</a> which is constant with respect to the length of the list (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O(1)}</annotation>

</semantics>

</math></span><img src="./55a2cd47ca6554fafc21bbef3331256c7e1631ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\textstyle O(1)}" loading="lazy"></span>). Timsort sorts the list in time <a href="Linearithmic" class="mw-redirect" title="Linearithmic">linearithmic</a> (proportional to a quantity times its logarithm) in the list's length (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O(n\log n)}</annotation>

</semantics>

</math></span><img src="./e300e6b542c2c33ac12df0f02c5047db8ee8e1ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\textstyle O(n\log n)}" loading="lazy"></span>), but has a space requirement <a href="Proportionality_(mathematics)" title="Proportionality (mathematics)">linear</a> in the length of the list (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O(n)}</annotation>

</semantics>

</math></span><img src="./e73234cd485b947e68d1d78823313db65ef226d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\textstyle O(n)}" loading="lazy"></span>). If large lists must be sorted at high speed for a given application, timsort is a better choice; however, if minimizing the <a href="Flash_memory#Memory_wear" title="Flash memory">program/erase cycles</a> and <a href="Memory_footprint" title="Memory footprint">memory footprint</a> of the sorting is more important, cycle sort is a better choice.

</p>

<div class="mw-heading mw-heading2"><h2 id="Background">Background</h2></div>

<p>The importance of efficiency with respect to time was emphasized by <a href="Ada_Lovelace" title="Ada Lovelace">Ada Lovelace</a> in 1843 as applied to <a href="Charles_Babbage" title="Charles Babbage">Charles Babbage</a>'s mechanical analytical engine:

</p>

<blockquote><p>"In almost every computation a great variety of arrangements for the succession of the processes is possible, and various considerations must influence the selections amongst them for the purposes of a calculating engine. One essential object is to choose that arrangement which shall tend to reduce to a minimum the time necessary for completing the calculation"<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></p></blockquote>

<p>Early <a href="Electronic_computer" class="mw-redirect" title="Electronic computer">electronic computers</a> had both limited <a href="Clock_cycle" class="mw-redirect" title="Clock cycle">speed</a> and limited <a href="Random_access_memory" class="mw-redirect" title="Random access memory">random access memory</a>. Therefore, a <a href="Space%E2%80%93time_trade-off" class="mw-redirect" title="Space–time trade-off">space–time trade-off</a> occurred. A <a href="Task_(computing)" title="Task (computing)">task</a> could use a fast algorithm using a lot of memory, or it could use a slow algorithm using little memory. The engineering trade-off was therefore to use the fastest algorithm that could fit in the available memory.

</p><p>Modern computers are significantly faster than early computers and have a much larger amount of memory available (<a href="Orders_of_magnitude_(computing)" class="mw-redirect" title="Orders of magnitude (computing)">gigabytes instead of kilobytes</a>). Nevertheless, <a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a> emphasized that efficiency is still an important consideration:

</p>

<blockquote><p> "In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal and I believe the same viewpoint should prevail in software engineering"<sup id="cite_ref-Knuth1974_2-0" class="reference"><a href="#cite_note-Knuth1974-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></p></blockquote>

<div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2></div>

<p>An algorithm is considered efficient if its resource consumption, also known as computational cost, is at or below some acceptable level. Roughly speaking, 'acceptable' means: it will run in a reasonable amount of time or space on an available computer, typically as a <a href="Function_(mathematics)" title="Function (mathematics)">function</a> of the size of the input. Since the 1950s computers have seen dramatic increases in both the available computational power and in the available amount of memory, so current acceptable levels would have been unacceptable even 10 years ago. In fact, thanks to the <a href="Moore's_law" title="Moore's law">approximate doubling of computer power every 2 years</a>, tasks that are acceptably efficient on modern <a href="Smartphone" title="Smartphone">smartphones</a> and <a href="Embedded_system" title="Embedded system">embedded systems</a> may have been unacceptably inefficient for industrial <a href="Server_(computing)" title="Server (computing)">servers</a> 10 years ago.

</p><p>Computer manufacturers frequently bring out new models, often with higher <a href="Computer_performance" title="Computer performance">performance</a>. Software costs can be quite high, so in some cases the simplest and cheapest way of getting higher performance might be to just buy a faster computer, provided it is <a href="Backward_compatibility" title="Backward compatibility">compatible</a> with an existing computer.

</p><p>There are many ways in which the resources used by an algorithm can be measured: the two most common measures are speed and memory usage; other measures could include transmission speed, temporary disk usage, long-term disk usage, power consumption, <a href="Total_cost_of_ownership" title="Total cost of ownership">total cost of ownership</a>, <a href="Response_time_(technology)" title="Response time (technology)">response time</a> to external stimuli, etc. Many of these measures depend on the size of the input to the algorithm, i.e. the amount of data to be processed. They might also depend on the way in which the data is arranged; for example, some <a href="Sorting_algorithm" title="Sorting algorithm">sorting algorithms</a> perform poorly on data which is already sorted, or which is sorted in reverse order.

</p><p>In practice, there are other factors which can affect the efficiency of an algorithm, such as requirements for accuracy and/or reliability. As detailed below, the way in which an algorithm is implemented can also have a significant effect on actual efficiency, though many aspects of this relate to <a href="Optimization_(computer_science)" class="mw-redirect" title="Optimization (computer science)">optimization</a> issues.

</p>

<div class="mw-heading mw-heading3"><h3 id="Theoretical_analysis">Theoretical analysis</h3></div>

<p>In the theoretical <a href="Analysis_of_algorithms" title="Analysis of algorithms">analysis of algorithms</a>, the normal practice is to estimate their complexity in the asymptotic sense. The most commonly used notation to describe resource consumption or "complexity" is <a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a>'s <a href="Big_O_notation" title="Big O notation">Big O notation</a>, representing the complexity of an algorithm as a function of the size of the input <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle n}</annotation>

</semantics>

</math></span><img src="./cc6e1f880981346a604257ebcacdef24c0aca2d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\textstyle n}" loading="lazy"></span>. Big O notation is an <a href="Asymptote" title="Asymptote">asymptotic</a> measure of function complexity, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle f(n)=O{\bigl (}g(n){\bigr )}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle f(n)=O{\bigl (}g(n){\bigr )}}</annotation>

</semantics>

</math></span><img src="./e763b207be3bc51ff39ea77eba50a518a2e76478.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.804ex; height:3.176ex;" alt="{\textstyle f(n)=O{\bigl (}g(n){\bigr )}}" loading="lazy"></span> roughly means the time requirement for an algorithm is proportional to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n)}</annotation>

</semantics>

</math></span><img src="./d4ad18070e494503403daf39398e711c1378348e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.32ex; height:2.843ex;" alt="{\displaystyle g(n)}" loading="lazy"></span>, omitting <a href="Lower-order_terms" class="mw-redirect" title="Lower-order terms">lower-order terms</a> that contribute less than <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n)}</annotation>

</semantics>

</math></span><img src="./d4ad18070e494503403daf39398e711c1378348e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.32ex; height:2.843ex;" alt="{\displaystyle g(n)}" loading="lazy"></span> to the growth of the function as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle n}</annotation>

</semantics>

</math></span><img src="./cc6e1f880981346a604257ebcacdef24c0aca2d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\textstyle n}" loading="lazy"></span> <a href="Limit_(mathematics)" title="Limit (mathematics)">grows arbitrarily large</a>. This estimate may be misleading when <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle n}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle n}</annotation>

</semantics>

</math></span><img src="./cc6e1f880981346a604257ebcacdef24c0aca2d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\textstyle n}" loading="lazy"></span> is large as the notation is asymptotic. For example, bubble sort may be faster than <a href="Merge_sort" title="Merge sort">merge sort</a> when only a few items are to be sorted; however either implementation is likely to meet performance requirements for a small list. Typically, programmers are interested in algorithms that <a href="Scalability" title="Scalability">scale</a> efficiently to large input sizes, and merge sort is preferred over bubble sort for lists of length encountered in most data-intensive programs.

</p><p>Some examples of Big O notation applied to algorithms' asymptotic time complexity include:

</p>

<th>Notation</th>

<th>Examples

</th></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math></span><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"></span></td>

<td><a href="Constant_time" class="mw-redirect" title="Constant time">constant</a></td>

<td>Finding the median from a sorted list of measurements; Using a constant-size <a href="Lookup_table" title="Lookup table">lookup table</a>; Using a suitable <a href="Hash_function" title="Hash function">hash function</a> for looking up an item.

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math></span><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"></span></td>

<td><a href="Logarithmic_time" class="mw-redirect" title="Logarithmic time">logarithmic</a></td>

<td>Finding an item in a sorted array with a <a href="Binary_search_algorithm" class="mw-redirect" title="Binary search algorithm">binary search</a> or a balanced search <a href="Tree_data_structure" class="mw-redirect" title="Tree data structure">tree</a> as well as all operations in a <a href="Binomial_heap" title="Binomial heap">Binomial heap</a>.

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math></span><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"></span></td>

<td><a href="Linear_time" class="mw-redirect" title="Linear time">linear</a></td>

<td>Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two <i>n</i>-bit integers by <a href="Ripple_carry_adder" class="mw-redirect" title="Ripple carry adder">ripple carry</a>.

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math></span><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"></span></td>

<td><a href="Linearithmic_time" class="mw-redirect" title="Linearithmic time">linearithmic</a>, loglinear, or quasilinear</td>

<td>Performing a <a href="Fast_Fourier_transform" title="Fast Fourier transform">Fast Fourier transform</a>; <a href="Heapsort" title="Heapsort">heapsort</a>, <a href="Quicksort" title="Quicksort">quicksort</a> (<a href="Best%2C_worst_and_average_case" title="Best, worst and average case">best and average case</a>), or <a href="Merge_sort" title="Merge sort">merge sort</a>

</td></tr>

<tr>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math></span><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"></span></td>

<td><a href="Quadratic_time" class="mw-redirect" title="Quadratic time">quadratic</a></td>

<td><a href="Multiplication" title="Multiplication">Multiplying</a> two <i>n</i>-digit numbers by <a href="Long_multiplication" class="mw-redirect" title="Long multiplication">a simple algorithm</a>; <a href="Bubble_sort" title="Bubble sort">bubble sort</a> (worst case or naive implementation), <a href="Shell_sort" class="mw-redirect" title="Shell sort">Shell sort</a>, quicksort (<a href="Best%2C_worst_and_average_case" title="Best, worst and average case">worst case</a>), <a href="Selection_sort" title="Selection sort">selection sort</a> or <a href="Insertion_sort" title="Insertion sort">insertion sort</a>

</td></tr>

<tr>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(c^{n}),\;c>1}</annotation>

</semantics>

</math></span><img src="./89f4ecbe75f2424973437985768adfe6652b1650.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.755ex; height:2.843ex;" alt="{\displaystyle O(c^{n}),\;c>1}" loading="lazy"></span></td>

<td><a href="Exponential_time" class="mw-redirect" title="Exponential time">exponential</a></td>

<td>Finding the optimal (non-<a href="Travelling_salesman_problem#Heuristic_and_approximation_algorithms" title="Travelling salesman problem">approximate</a>) solution to the <a href="Travelling_salesman_problem" title="Travelling salesman problem">travelling salesman problem</a> using <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a>; <a href="Boolean_satisfiability_problem" title="Boolean satisfiability problem">determining if two logical statements are equivalent</a> using <a href="Brute-force_search" title="Brute-force search">brute-force search</a>

</td></tr></tbody></table>

<div class="mw-heading mw-heading3"><h3 id="Measuring_performance">Measuring performance</h3></div>

<p>For new versions of software or to provide comparisons with competitive systems, <a href="Benchmark_(computing)" title="Benchmark (computing)">benchmarks</a> are sometimes used, which assist with gauging an algorithms relative performance. If a new <a href="Sorting_algorithm" title="Sorting algorithm">sort algorithm</a> is produced, for example, it can be compared with its predecessors to ensure that at least it is efficient as before with known data, taking into consideration any functional improvements. Benchmarks can be used by customers when comparing various products from alternative suppliers to estimate which product will best suit their specific requirements in terms of functionality and performance. For example, in the <a href="Mainframe_computer" title="Mainframe computer">mainframe</a> world certain proprietary <a href="Mainframe_sort_merge" title="Mainframe sort merge">sort</a> products from independent software companies such as <a href="Syncsort" class="mw-redirect" title="Syncsort">Syncsort</a> compete with products from the major suppliers such as <a href="IBM" title="IBM">IBM</a> for speed.

</p><p>Some benchmarks provide opportunities for producing an analysis comparing the relative speed of various compiled and interpreted languages for example<sup id="cite_ref-fourmilab.ch_3-0" class="reference"><a href="#cite_note-fourmilab.ch-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

and <a href="The_Computer_Language_Benchmarks_Game" title="The Computer Language Benchmarks Game">The Computer Language Benchmarks Game</a> compares the performance of implementations of typical programming problems in several programming languages.

</p><p>Even creating "<a href="Do_it_yourself" title="Do it yourself">do it yourself</a>" benchmarks can demonstrate the relative performance of different programming languages, using a variety of user specified criteria. This is quite simple, as a "Nine language performance roundup" by Christopher W. Cowell-Shah demonstrates by example.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Implementation_concerns">Implementation concerns</h3></div>

<p>Implementation issues can also have an effect on efficiency, such as the choice of programming language, or the way in which the algorithm is actually coded,<sup id="cite_ref-KriegelSchubert2016_6-0" class="reference"><a href="#cite_note-KriegelSchubert2016-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> or the choice of a <a href="Compiler" title="Compiler">compiler</a> for a particular language, or the <a href="Compiler_optimization" class="mw-redirect" title="Compiler optimization">compilation options</a> used, or even the <a href="Operating_system" title="Operating system">operating system</a> being used. In many cases a language implemented by an <a href="Interpreter_(computing)" title="Interpreter (computing)">interpreter</a> may be much slower than a language implemented by a compiler.<sup id="cite_ref-fourmilab.ch_3-1" class="reference"><a href="#cite_note-fourmilab.ch-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> See the articles on <a href="Just-in-time_compilation" title="Just-in-time compilation">just-in-time compilation</a> and <a href="Interpreted_language" class="mw-redirect" title="Interpreted language">interpreted languages</a>.

</p><p>There are other factors which may affect time or space issues, but which may be outside of a programmer's control; these include <a href="Data_alignment" class="mw-redirect" title="Data alignment">data alignment</a>, <a href="Granularity#Data_granularity" title="Granularity">data granularity</a>, <a href="Locality_of_reference" title="Locality of reference">cache locality</a>, <a href="Cache_coherence" title="Cache coherence">cache coherency</a>, <a href="Garbage_collection_(computer_science)" title="Garbage collection (computer science)">garbage collection</a>, <a href="Instruction-level_parallelism" title="Instruction-level parallelism">instruction-level parallelism</a>, <a href="Multithreading_(disambiguation)" class="mw-redirect mw-disambig" title="Multithreading (disambiguation)">multi-threading</a> (at either a hardware or software level), <a href="Simultaneous_multithreading" title="Simultaneous multithreading">simultaneous multitasking</a>, and <a href="Subroutine" class="mw-redirect" title="Subroutine">subroutine</a> calls.<sup id="cite_ref-steele1997_7-0" class="reference"><a href="#cite_note-steele1997-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p><p>Some processors have capabilities for <a href="Vector_processor" title="Vector processor">vector processing</a>, which allow a <a href="SIMD" class="mw-redirect" title="SIMD">single instruction to operate on multiple operands</a>; it may or may not be easy for a programmer or compiler to use these capabilities. Algorithms designed for sequential processing may need to be completely redesigned to make use of <a href="Parallel_computing" title="Parallel computing">parallel processing</a>, or they could be easily reconfigured. As <a href="Parallel_computing" title="Parallel computing">parallel</a> and <a href="Distributed_computing" title="Distributed computing">distributed computing</a> grow in importance in the late 2010s, more investments are being made into efficient <a href="High-level_programming_language" title="High-level programming language">high-level</a> <a href="Application_programming_interface" class="mw-redirect" title="Application programming interface">APIs</a> for parallel and distributed computing systems such as <a href="CUDA" title="CUDA">CUDA</a>, <a href="TensorFlow" title="TensorFlow">TensorFlow</a>, <a href="Apache_Hadoop" title="Apache Hadoop">Hadoop</a>, <a href="OpenMP" title="OpenMP">OpenMP</a> and <a href="Message_Passing_Interface" title="Message Passing Interface">MPI</a>.

</p><p>Another problem which can arise in programming is that processors compatible with the same <a href="Instruction_set_architecture" title="Instruction set architecture">instruction set</a> (such as <a href="X86-64" title="X86-64">x86-64</a> or <a href="ARM_architecture" class="mw-redirect" title="ARM architecture">ARM</a>) may implement an instruction in different ways, so that instructions which are relatively fast on some models may be relatively slow on other models. This often presents challenges to <a href="Optimizing_compiler" title="Optimizing compiler">optimizing compilers</a>, which must have extensive knowledge of the specific <a href="Central_processing_unit" title="Central processing unit">CPU</a> and other hardware available on the compilation target to best optimize a program for performance. In the extreme case, a compiler may be forced to <a href="Software_emulation" class="mw-redirect" title="Software emulation">emulate</a> instructions not supported on a compilation target platform, forcing it to <a href="Code_generation_(compiler)" title="Code generation (compiler)">generate code</a> or <a href="Linking_(computing)" class="mw-redirect" title="Linking (computing)">link</a> an external <a href="Library_(computing)" title="Library (computing)">library call</a> to produce a result that is otherwise incomputable on that platform, even if it is natively supported and more efficient in hardware on other platforms. This is often the case in <a href="Embedded_system" title="Embedded system">embedded systems</a> with respect to <a href="Floating-point_arithmetic" title="Floating-point arithmetic">floating-point arithmetic</a>, where small and <a href="Low-power_computing" class="mw-redirect" title="Low-power computing">low-power</a> <a href="Microcontroller" title="Microcontroller">microcontrollers</a> often lack hardware support for floating-point arithmetic and thus require computationally expensive software routines to produce floating point calculations.

</p>

<div class="mw-heading mw-heading2"><h2 id="Measures_of_resource_usage">Measures of resource usage</h2></div>

<p>Measures are normally expressed as a function of the size of the input <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle {n}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \scriptstyle {n}}</annotation>

</semantics>

</math></span><img src="./4108828bc4534897ce3e5e92aba9d8c5de06392a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.986ex; height:1.343ex;" alt="{\displaystyle \scriptstyle {n}}" loading="lazy"></span>.

</p><p>The two most common measures are:

</p>

<ul><li><i>Time</i>: how long does the algorithm take to complete?</li>

<li><i>Space</i>: how much working memory (typically RAM) is needed by the algorithm? This has two aspects: the amount of memory needed by the code (auxiliary space usage), and the amount of memory needed for the data on which the code operates (intrinsic space usage).</li></ul>

<p>For computers whose power is supplied by a battery (e.g. <a href="Laptop" title="Laptop">laptops</a> and <a href="Smartphone" title="Smartphone">smartphones</a>), or for very long/large calculations (e.g. <a href="Supercomputer" title="Supercomputer">supercomputers</a>), other measures of interest are:

</p>

<ul><li><i>Direct power consumption</i>: power needed directly to operate the computer.</li>

<li><i>Indirect power consumption</i>: power needed for cooling, lighting, etc.</li></ul>

<p>As of 2018, power consumption is growing as an important metric for computational tasks of all types and at all scales ranging from <a href="Embedded_system" title="Embedded system">embedded</a> <a href="Internet_of_things" title="Internet of things">Internet of things</a> devices to <a href="System-on-chip" class="mw-redirect" title="System-on-chip">system-on-chip</a> devices to <a href="Server_farm" title="Server farm">server farms</a>. This trend is often referred to as <a href="Green_computing" title="Green computing">green computing</a>.

</p><p>Less common measures of computational efficiency may also be relevant in some cases:

</p>

<ul><li><i>Transmission size</i>: bandwidth could be a limiting factor. <a href="Data_compression" title="Data compression">Data compression</a> can be used to reduce the amount of data to be transmitted. Displaying a picture or image (e.g. Google logo) can result in transmitting tens of thousands of bytes (48K in this case) compared with transmitting six bytes for the text "Google". This is important for <a href="I/O_bound_computing" class="mw-redirect" title="I/O bound computing">I/O bound computing</a> tasks.</li>

<li><i>External space</i>: space needed on a disk or other external memory device; this could be for temporary storage while the algorithm is being carried out, or it could be long-term storage needed to be carried forward for future reference.</li>

<li><i>Response time</i> (<a href="Latency_(engineering)" title="Latency (engineering)">latency</a>): this is particularly relevant in a <a href="Real-time_computing" title="Real-time computing">real-time application</a> when the computer system must <a href="Event-driven_programming" title="Event-driven programming">respond quickly to some external event</a>.</li>

<li><i>Total cost of ownership</i>: particularly if a computer is dedicated to one particular algorithm.</li></ul>

<div class="mw-heading mw-heading4"><h4 id="Theory">Theory</h4></div>

<p><a href="Analysis_of_algorithms" title="Analysis of algorithms">Analysis of algorithms</a>, typically using concepts like <a href="Time_complexity" title="Time complexity">time complexity</a>, can be used to get an estimate of the running time as a function of the size of the input data. The result is normally expressed using <a href="Big_O_notation" title="Big O notation">Big O notation</a>. This is useful for comparing algorithms, especially when a large amount of data is to be processed. More detailed estimates are needed to compare algorithm performance when the amount of data is small, although this is likely to be of less importance. <a href="Parallel_algorithm" title="Parallel algorithm">Parallel algorithms</a> may be <a href="Analysis_of_parallel_algorithms" title="Analysis of parallel algorithms">more difficult to analyze</a>.

</p>

<div class="mw-heading mw-heading4"><h4 id="Practice">Practice</h4></div>

<p>A <a href="Benchmark_(computing)" title="Benchmark (computing)">benchmark</a> can be used to assess the performance of an algorithm in practice. Many programming languages have an available function which provides <a href="CPU_time" title="CPU time">CPU time</a> usage. For long-running algorithms the elapsed time could also be of interest. Results should generally be averaged over several tests.

</p><p>Run-based profiling can be very sensitive to hardware configuration and the possibility of other programs or tasks running at the same time in a <a href="Multi-processing" class="mw-redirect" title="Multi-processing">multi-processing</a> and <a href="Multi-programming" class="mw-redirect" title="Multi-programming">multi-programming</a> environment.

</p><p>This sort of test also depends heavily on the selection of a particular programming language, compiler, and compiler options, so algorithms being compared must all be implemented under the same conditions.

</p>

<div class="mw-heading mw-heading3"><h3 id="Space">Space</h3></div>

<p>This section is concerned with use of memory resources (<a href="Processor_register" title="Processor register">registers</a>, <a href="Cache_(computing)" title="Cache (computing)">cache</a>, <a href="Random-access_memory" title="Random-access memory">RAM</a>, <a href="Virtual_memory" title="Virtual memory">virtual memory</a>, <a href="Auxiliary_memory" class="mw-redirect" title="Auxiliary memory">secondary memory</a>) while the algorithm is being executed. As for time analysis above, <a href="Analysis_of_algorithms" title="Analysis of algorithms">analyze</a> the algorithm, typically using <a href="Space_complexity" title="Space complexity">space complexity</a> analysis to get an estimate of the run-time memory needed as a function as the size of the input data. The result is normally expressed using <a href="Big_O_notation" title="Big O notation">Big O notation</a>.

</p><p>There are up to four aspects of memory usage to consider:

</p>

<ul><li>The amount of memory needed to hold the code for the algorithm.</li>

<li>The amount of memory needed for the <a href="Input_(computer_science)" title="Input (computer science)">input data</a>.</li>

<li>The amount of memory needed for any <a href="Output_(computing)" class="mw-redirect" title="Output (computing)">output data</a>.

<ul><li>Some algorithms, such as sorting, often <a href="In-place_algorithm" title="In-place algorithm">rearrange the input data</a> and do not need any additional space for output data. This property is referred to as "<a href="In-place_algorithm" title="In-place algorithm">in-place</a>" operation.</li></ul></li>

<li>The amount of memory needed as working space during the calculation.

<ul><li>This includes <a href="Local_variable" title="Local variable">local variables</a> and any <a href="Local_variables%2C_recursion_and_reentrancy" class="mw-redirect" title="Local variables, recursion and reentrancy">stack space needed</a> by <a href="Function_call" class="mw-redirect" title="Function call">routines called</a> during a calculation; this stack space can be significant for algorithms which use <a href="Recursion_(computer_science)" title="Recursion (computer science)">recursive</a> techniques.</li></ul></li></ul>

<p>Early electronic computers, and early home computers, had relatively small amounts of working memory. For example, the 1949 <a href="Electronic_Delay_Storage_Automatic_Calculator" class="mw-redirect" title="Electronic Delay Storage Automatic Calculator">Electronic Delay Storage Automatic Calculator</a> (EDSAC) had a maximum working memory of 1024 17-bit words, while the 1980 Sinclair <a href="ZX80" title="ZX80">ZX80</a> came initially with 1024 8-bit bytes of working memory. In the late 2010s, it is typical for <a href="Personal_computer" title="Personal computer">personal computers</a> to have between 4 and 32 <a href="Gigabyte" title="Gigabyte">GB</a> of RAM, an increase of over 300 million times as much memory.

</p>

<div class="mw-heading mw-heading4"><h4 id="Caching_and_memory_hierarchy">Caching and memory hierarchy</h4></div>

<div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Memory_hierarchy" title="Memory hierarchy">Memory hierarchy</a></div>

<p>Modern computers can have relatively large amounts of memory (possibly gigabytes), so having to squeeze an algorithm into a confined amount of memory is not the kind of problem it used to be. However, the different types of memory and their relative access speeds can be significant:

</p>

<ul><li><a href="Processor_register" title="Processor register">Processor registers</a>, are the fastest memory with the least amount of space. Most direct computation on modern computers occurs with source and destination operands in registers before being updated to the cache, main memory and virtual memory if needed. On a <a href="CPU_core" class="mw-redirect" title="CPU core">processor core</a>, there are typically on the order of hundreds of bytes or fewer of register availability, although a <a href="Register_file" title="Register file">register file</a> may contain more physical registers than <a href="Instruction_set_architecture" title="Instruction set architecture">architectural</a> registers defined in the instruction set architecture.</li>

<li><a href="CPU_cache" title="CPU cache">Cache memory</a> is the second fastest, and second smallest, available in the memory hierarchy. Caches are present in processors such as CPUs or GPUs, where they are typically implemented in <a href="Static_random-access_memory" title="Static random-access memory">static RAM</a>, though they can also be found in peripherals such as disk drives. Processor caches often have their own <a href="Cache_hierarchy" title="Cache hierarchy">multi-level hierarchy</a>; lower levels are larger, slower and typically <a href="Shared_cache" class="mw-redirect" title="Shared cache">shared</a> between <a href="Processor_core" class="mw-redirect" title="Processor core">processor cores</a> in <a href="Multi-core_processor" title="Multi-core processor">multi-core processors</a>. In order to process operands in cache memory, a <a href="Processor_(computing)" title="Processor (computing)">processing unit</a> must fetch the data from the cache, perform the operation in registers and write the data back to the cache. This operates at speeds comparable (about 2-10 times slower) with the CPU or GPU's <a href="Arithmetic_logic_unit" title="Arithmetic logic unit">arithmetic logic unit</a> or <a href="Floating-point_unit" title="Floating-point unit">floating-point unit</a> if in the <a href="L1_cache" class="mw-redirect" title="L1 cache">L1 cache</a>.<sup id="cite_ref-CompArc:QuantApp_8-0" class="reference"><a href="#cite_note-CompArc:QuantApp-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> It is about 10 times slower if there is an L1 <a href="Cache_miss" class="mw-redirect" title="Cache miss">cache miss</a> and it must be retrieved from and written to the <a href="L2_cache" class="mw-redirect" title="L2 cache">L2 cache</a>, and a further 10 times slower if there is an L2 cache miss and it must be retrieved from an <a href="L3_cache" class="mw-redirect" title="L3 cache">L3 cache</a>, if present.</li>

<li><a href="Main_memory" class="mw-redirect" title="Main memory">Main physical memory</a> is most often implemented in <a href="Dynamic_RAM" class="mw-redirect" title="Dynamic RAM">dynamic RAM</a> (DRAM). The main memory is much larger (typically <a href="Gigabyte" title="Gigabyte">gigabytes</a> compared to ≈8 <a href="Megabyte" title="Megabyte">megabytes</a>) than an L3 CPU cache, with read and write latencies typically 10-100 times slower.<sup id="cite_ref-CompArc:QuantApp_8-1" class="reference"><a href="#cite_note-CompArc:QuantApp-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> As of 2018, RAM is increasingly implemented <a href="System-on-chip" class="mw-redirect" title="System-on-chip">on-chip</a> of processors, as CPU or <a href="GPU_memory" class="mw-redirect" title="GPU memory">GPU memory</a>.</li>

<li><a href="Paged_memory" class="mw-redirect" title="Paged memory">Paged memory</a>, often used for <a href="Virtual_memory" title="Virtual memory">virtual memory</a> management, is memory stored in <a href="Secondary_storage" class="mw-redirect" title="Secondary storage">secondary storage</a> such as a <a href="Hard_disk" class="mw-redirect" title="Hard disk">hard disk</a>, and is an extension to the <a href="Memory_hierarchy" title="Memory hierarchy">memory hierarchy</a> which allows use of a potentially larger storage space, at the cost of much higher latency, typically around 1000 times slower than a <a href="Cache_miss" class="mw-redirect" title="Cache miss">cache miss</a> for a value in RAM.<sup id="cite_ref-CompArc:QuantApp_8-2" class="reference"><a href="#cite_note-CompArc:QuantApp-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> While originally motivated to create the impression of higher amounts of memory being available than were truly available, virtual memory is more important in contemporary usage for its <a href="Time-space_tradeoff" class="mw-redirect" title="Time-space tradeoff">time-space tradeoff</a> and enabling the usage of <a href="Virtual_machine" title="Virtual machine">virtual machines</a>.<sup id="cite_ref-CompArc:QuantApp_8-3" class="reference"><a href="#cite_note-CompArc:QuantApp-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> Cache misses from main memory are called <a href="Page_fault" title="Page fault">page faults</a>, and incur huge performance penalties on programs.</li></ul>

<p>An algorithm whose memory needs will fit in cache memory will be much faster than an algorithm which fits in main memory, which in turn will be very much faster than an algorithm which has to resort to paging. Because of this, <a href="Cache_replacement_policies" title="Cache replacement policies">cache replacement policies</a> are extremely important to high-performance computing, as are <a href="Cache-aware_model" class="mw-redirect" title="Cache-aware model">cache-aware programming</a> and <a href="Data_alignment" class="mw-redirect" title="Data alignment">data alignment</a>. To further complicate the issue, some systems have up to three levels of cache memory, with varying effective speeds. Different systems will have different amounts of these various types of memory, so the effect of algorithm memory needs can vary greatly from one system to another.

</p><p>In the early days of electronic computing, if an algorithm and its data would not fit in main memory then the algorithm could not be used. Nowadays the use of virtual memory appears to provide much more memory, but at the cost of performance. Much higher speed can be obtained if an algorithm and its data fit in cache memory; in this case minimizing space will also help minimize time. This is called the <a href="Principle_of_locality" title="Principle of locality">principle of locality</a>, and can be subdivided into <a href="Locality_of_reference" title="Locality of reference">locality of reference</a>, <a href="Spatial_locality" class="mw-redirect" title="Spatial locality">spatial locality</a>, and <a href="Temporal_locality" class="mw-redirect" title="Temporal locality">temporal locality</a>. An algorithm which will not fit completely in cache memory but which exhibits locality of reference may perform reasonably well.

</p>

<ul><li><a href="Analysis_of_algorithms" title="Analysis of algorithms">Analysis of algorithms</a>—how to determine the resources needed by an algorithm</li>

<li><a href="Benchmark_(computing)" title="Benchmark (computing)">Benchmark</a>—a method for measuring comparative execution times in defined cases</li>

<li><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Best, worst and average case</a>—considerations for estimating execution times in three scenarios</li>

<li><a href="Compiler_optimization" class="mw-redirect" title="Compiler optimization">Compiler optimization</a>—compiler-derived optimization</li>

<li><a href="Computational_complexity_theory" title="Computational complexity theory">Computational complexity theory</a></li>

<li><a href="Computer_performance" title="Computer performance">Computer performance</a>—computer hardware metrics</li>

<li><a href="Empirical_algorithmics" title="Empirical algorithmics">Empirical algorithmics</a>—the practice of using empirical methods to study the behavior of algorithms</li>

<li><a href="Program_optimization" title="Program optimization">Program optimization</a></li>

<li><a href="Profiling_(computer_programming)" title="Profiling (computer programming)">Performance analysis</a>—methods of measuring actual performance of an algorithm at run-time</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGreen" class="citation cs2">Green, Christopher, <a rel="nofollow" class="external text" href="http://psychclassics.yorku.ca/Lovelace/lovelace.htm"><i>Classics in the History of Psychology</i></a><span class="reference-accessdate">, retrieved <span class="nowrap">19 May</span> 2013</span></cite></span>

</li>

<li id="cite_note-Knuth1974-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Knuth1974_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFKnuth1974" class="citation cs2">Knuth, Donald (1974), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20090824073244/http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf">"Structured Programming with go-to Statements"</a> <span class="cs1-format">(PDF)</span>, <i>Computing Surveys</i>, <b>6</b> (4): <span class="nowrap">261–</span>301, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.6084">10.1.1.103.6084</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F356635.356640">10.1145/356635.356640</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207630080">207630080</a>, archived from <a rel="nofollow" class="external text" href="http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 24 August 2009<span class="reference-accessdate">, retrieved <span class="nowrap">19 May</span> 2013</span></cite></span>

</li>

<li id="cite_note-fourmilab.ch-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-fourmilab.ch_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-fourmilab.ch_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.fourmilab.ch/fourmilog/archives/2005-08/000567.html">"Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason)"</a>. Fourmilab.ch. 4 August 2005<span class="reference-accessdate">. Retrieved <span class="nowrap">14 December</span> 2011</span>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.roylongbottom.org.uk/whetstone.htm#anchorPC2">"Whetstone Benchmark History"</a>. Roylongbottom.org.uk<span class="reference-accessdate">. Retrieved <span class="nowrap">14 December</span> 2011</span>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFOSNews_Staff" class="citation web cs1">OSNews Staff. <a rel="nofollow" class="external text" href="http://www.osnews.com/story/5602">"Nine Language Performance Round-up: Benchmarking Math & File I/O"</a>. <i>osnews.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">18 September</span> 2018</span>.</cite></span>

</li>

<li id="cite_note-KriegelSchubert2016-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-KriegelSchubert2016_6-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFKriegelSchubertZimek2016" class="citation journal cs1"><a href="Hans-Peter_Kriegel" title="Hans-Peter Kriegel">Kriegel, Hans-Peter</a>; Schubert, Erich; <a href="Arthur_Zimek" title="Arthur Zimek">Zimek, Arthur</a> (2016). "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". <i>Knowledge and Information Systems</i>. <b>52</b> (2): <span class="nowrap">341–</span>378. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10115-016-1004-2">10.1007/s10115-016-1004-2</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0219-1377">0219-1377</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:40772241">40772241</a>.</cite></span>

</li>

<li id="cite_note-steele1997-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-steele1997_7-0">^</a></b></span> <span class="reference-text">Guy Lewis Steele, Jr. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977.<a rel="nofollow" class="external autonumber" href="http://dspace.mit.edu/handle/1721.1/5753">[1]</a></span>

</li>

<li id="cite_note-CompArc:QuantApp-8"><span class="mw-cite-backlink">^ <a href="#cite_ref-CompArc:QuantApp_8-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-CompArc:QuantApp_8-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-CompArc:QuantApp_8-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-CompArc:QuantApp_8-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFHennessyPattersonAsanovićBakos2011" class="citation book cs1">Hennessy, John L; Patterson, David A; <a href="Krste_Asanovi%C4%87" title="Krste Asanović">Asanović, Krste</a>; Bakos, Jason D; Colwell, Robert P; Bhattacharjee, Abhishek; Conte, Thomas M; Duato, José; Franklin, Diana; Goldberg, David; <a href="Norman_Jouppi" title="Norman Jouppi">Jouppi, Norman P</a>; Li, Sheng; Muralimanohar, Naveen; Peterson, Gregory D; Pinkston, Timothy Mark; Ranganathan, Prakash; Wood, David Allen; Young, Clifford; Zaky, Amr (2011). <i>Computer Architecture: a Quantitative Approach</i> (Sixth ed.). Elsevier Science. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0128119051</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/983459758">983459758</a>.</cite></span>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Computer_science1050" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Computer_science1050" style="font-size:114%;margin:0 4em"><a href="Computer_science" title="Computer science">Computer science</a></div></th></tr><tr><td class="navbox-abovebelow" colspan="2"><div>Note: This template roughly follows the 2012 <a href="ACM_Computing_Classification_System" title="ACM Computing Classification System">ACM Computing Classification System</a>.</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_hardware" title="Computer hardware">Hardware</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Printed_circuit_board" title="Printed circuit board">Printed circuit board</a></li>

<li><a href="Peripheral" title="Peripheral">Peripheral</a></li>

<li><a href="Integrated_circuit" title="Integrated circuit">Integrated circuit</a></li>

<li><a href="Very-large-scale_integration" title="Very-large-scale integration">Very-large-scale integration</a></li>

<li><a href="System_on_a_chip" title="System on a chip">System on a chip</a> (SoC)</li>

<li><a href="Green_computing" title="Green computing">Energy consumption</a> (green computing)</li>

<li><a href="Electronic_design_automation" title="Electronic design automation">Electronic design automation</a></li>

<li><a href="Hardware_acceleration" title="Hardware acceleration">Hardware acceleration</a></li>

<li><a href="Processor_(computing)" title="Processor (computing)">Processor</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Computer systems organization</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Computer_architecture" title="Computer architecture">Computer architecture</a></li>

<li><a href="Computational_complexity" title="Computational complexity">Computational complexity</a></li>

<li><a href="Dependability" title="Dependability">Dependability</a></li>

<li><a href="Embedded_system" title="Embedded system">Embedded system</a></li>

<li><a href="Real-time_computing" title="Real-time computing">Real-time computing</a></li>

<li><a href="Cyber-physical_system" title="Cyber-physical system">Cyber-physical system</a></li>

<li><a href="Fault_tolerance" title="Fault tolerance">Fault tolerance</a></li>

<li><a href="Wireless_sensor_network" title="Wireless sensor network">Wireless sensor network</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_network" title="Computer network">Networks</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Network_architecture" title="Network architecture">Network architecture</a></li>

<li><a href="Communication_protocol" title="Communication protocol">Network protocol</a></li>

<li><a href="Networking_hardware" title="Networking hardware">Network components</a></li>

<li><a href="Network_scheduler" title="Network scheduler">Network scheduler</a></li>

<li><a href="Network_performance" title="Network performance">Network performance evaluation</a></li>

<li><a href="Network_service" title="Network service">Network service</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Software organization</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interpreter_(computing)" title="Interpreter (computing)">Interpreter</a></li>

<li><a href="Middleware" title="Middleware">Middleware</a></li>

<li><a href="Virtual_machine" title="Virtual machine">Virtual machine</a></li>

<li><a href="Operating_system" title="Operating system">Operating system</a></li>

<li><a href="Software_quality" title="Software quality">Software quality</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Programming_language_theory" title="Programming language theory">Software notations</a> and <a href="Programming_tool" title="Programming tool">tools</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Programming_paradigm" title="Programming paradigm">Programming paradigm</a></li>

<li><a href="Programming_language" title="Programming language">Programming language</a></li>

<li><a href="Compiler_construction" class="mw-redirect" title="Compiler construction">Compiler</a></li>

<li><a href="Domain-specific_language" title="Domain-specific language">Domain-specific language</a></li>

<li><a href="Modeling_language" title="Modeling language">Modeling language</a></li>

<li><a href="Software_framework" title="Software framework">Software framework</a></li>

<li><a href="Integrated_development_environment" title="Integrated development environment">Integrated development environment</a></li>

<li><a href="Software_configuration_management" title="Software configuration management">Software configuration management</a></li>

<li><a href="Library_(computing)" title="Library (computing)">Software library</a></li>

<li><a href="Software_repository" title="Software repository">Software repository</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Software_development" title="Software development">Software development</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Control_flow" title="Control flow">Control variable</a></li>

<li><a href="Software_development_process" title="Software development process">Software development process</a></li>

<li><a href="Requirements_analysis" title="Requirements analysis">Requirements analysis</a></li>

<li><a href="Software_design" title="Software design">Software design</a></li>

<li><a href="Software_construction" title="Software construction">Software construction</a></li>

<li><a href="Software_deployment" title="Software deployment">Software deployment</a></li>

<li><a href="Software_engineering" title="Software engineering">Software engineering</a></li>

<li><a href="Software_maintenance" title="Software maintenance">Software maintenance</a></li>

<li><a href="Programming_team" title="Programming team">Programming team</a></li>

<li><a href="Open-source_software" title="Open-source software">Open-source model</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Theory_of_computation" title="Theory of computation">Theory of computation</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Model_of_computation" title="Model of computation">Model of computation</a>

<ul><li><a href="Stochastic_computing" title="Stochastic computing">Stochastic</a></li></ul></li>

<li><a href="Formal_language" title="Formal language">Formal language</a></li>

<li><a href="Automata_theory" title="Automata theory">Automata theory</a></li>

<li><a href="Computability_theory" title="Computability theory">Computability theory</a></li>

<li><a href="Computational_complexity_theory" title="Computational complexity theory">Computational complexity theory</a></li>

<li><a href="Logic_in_computer_science" title="Logic in computer science">Logic</a></li>

<li><a href="Semantics_(computer_science)" title="Semantics (computer science)">Semantics</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Algorithm" title="Algorithm">Algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Algorithm_design" class="mw-redirect" title="Algorithm design">Algorithm design</a></li>

<li><a href="Analysis_of_algorithms" title="Analysis of algorithms">Analysis of algorithms</a></li>

<li><a href="Randomized_algorithm" title="Randomized algorithm">Randomized algorithm</a></li>

<li><a href="Computational_geometry" title="Computational geometry">Computational geometry</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Mathematics of <a href="Computing" title="Computing">computing</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Discrete_mathematics" title="Discrete mathematics">Discrete mathematics</a></li>

<li><a href="Probability" title="Probability">Probability</a></li>

<li><a href="Statistics" title="Statistics">Statistics</a></li>

<li><a href="Mathematical_software" title="Mathematical software">Mathematical software</a></li>

<li><a href="Information_theory" title="Information theory">Information theory</a></li>

<li><a href="Mathematical_analysis" title="Mathematical analysis">Mathematical analysis</a></li>

<li><a href="Numerical_analysis" title="Numerical analysis">Numerical analysis</a></li>

<li><a href="Theoretical_computer_science" title="Theoretical computer science">Theoretical computer science</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Information_system" title="Information system">Information systems</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Database" title="Database">Database management system</a></li>

<li><a href="Computer_data_storage" title="Computer data storage">Information storage systems</a></li>

<li><a href="Enterprise_information_system" title="Enterprise information system">Enterprise information system</a></li>

<li><a href="Social_software" title="Social software">Social information systems</a></li>

<li><a href="Geographic_information_system" title="Geographic information system">Geographic information system</a></li>

<li><a href="Decision_support_system" title="Decision support system">Decision support system</a></li>

<li><a href="Industrial_process_control" title="Industrial process control">Process control system</a></li>

<li><a href="Multimedia_database" title="Multimedia database">Multimedia information system</a></li>

<li><a href="Data_mining" title="Data mining">Data mining</a></li>

<li><a href="Digital_library" title="Digital library">Digital library</a></li>

<li><a href="Computing_platform" title="Computing platform">Computing platform</a></li>

<li><a href="Digital_marketing" title="Digital marketing">Digital marketing</a></li>

<li><a href="World_Wide_Web" title="World Wide Web">World Wide Web</a></li>

<li><a href="Information_retrieval" title="Information retrieval">Information retrieval</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_security" title="Computer security">Security</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cryptography" title="Cryptography">Cryptography</a></li>

<li><a href="Formal_methods" title="Formal methods">Formal methods</a></li>

<li><a href="Security_hacker" title="Security hacker">Security hacker</a></li>

<li><a href="Security_service_(telecommunication)" title="Security service (telecommunication)">Security services</a></li>

<li><a href="Intrusion_detection_system" title="Intrusion detection system">Intrusion detection system</a></li>

<li><a href="Hardware_security" title="Hardware security">Hardware security</a></li>

<li><a href="Network_security" title="Network security">Network security</a></li>

<li><a href="Information_security" title="Information security">Information security</a></li>

<li><a href="Application_security" title="Application security">Application security</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a class="external text external" href="https://en.wikipedia.org/wiki/Human-centered_computing">Human–centered computing</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interaction_design" title="Interaction design">Interaction design</a></li>

<li><a href="Augmented_reality" title="Augmented reality">Augmented reality</a></li>

<li><a href="Virtual_reality" title="Virtual reality">Virtual reality</a></li>

<li><a href="Social_computing" title="Social computing">Social computing</a></li>

<li><a href="Ubiquitous_computing" title="Ubiquitous computing">Ubiquitous computing</a></li>

<li><a href="Visualization_(graphics)" title="Visualization (graphics)">Visualization</a></li>

<li><a href="Computer_accessibility" title="Computer accessibility">Accessibility</a></li>

<li><a href="Human%E2%80%93computer_interaction" title="Human–computer interaction">Human–computer interaction</a></li>

<li><a href="Mobile_computing" title="Mobile computing">Mobile computing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Concurrency_(computer_science)" title="Concurrency (computer science)">Concurrency</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Concurrent_computing" title="Concurrent computing">Concurrent computing</a></li>

<li><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></li>

<li><a href="Distributed_computing" title="Distributed computing">Distributed computing</a></li>

<li><a href="Multithreading_(computer_architecture)" title="Multithreading (computer architecture)">Multithreading</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Artificial_intelligence" title="Artificial intelligence">Artificial intelligence</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Natural_language_processing" title="Natural language processing">Natural language processing</a></li>

<li><a href="Knowledge_representation_and_reasoning" title="Knowledge representation and reasoning">Knowledge representation and reasoning</a></li>

<li><a href="Computer_vision" title="Computer vision">Computer vision</a></li>

<li><a href="Automated_planning_and_scheduling" title="Automated planning and scheduling">Automated planning and scheduling</a></li>

<li><a href="Mathematical_optimization" title="Mathematical optimization">Search methodology</a></li>

<li><a href="Control_theory" title="Control theory">Control method</a></li>

<li><a href="Philosophy_of_artificial_intelligence" title="Philosophy of artificial intelligence">Philosophy of artificial intelligence</a></li>

<li><a href="Distributed_artificial_intelligence" title="Distributed artificial intelligence">Distributed artificial intelligence</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Machine_learning" title="Machine learning">Machine learning</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Supervised_learning" title="Supervised learning">Supervised learning</a></li>

<li><a href="Unsupervised_learning" title="Unsupervised learning">Unsupervised learning</a></li>

<li><a href="Reinforcement_learning" title="Reinforcement learning">Reinforcement learning</a></li>

<li><a href="Multi-task_learning" title="Multi-task learning">Multi-task learning</a></li>

<li><a href="Cross-validation_(statistics)" title="Cross-validation (statistics)">Cross-validation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_graphics" title="Computer graphics">Graphics</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Computer_animation" title="Computer animation">Animation</a></li>

<li><a href="Rendering_(computer_graphics)" title="Rendering (computer graphics)">Rendering</a></li>

<li><a href="Photograph_manipulation" title="Photograph manipulation">Photograph manipulation</a></li>

<li><a href="Graphics_processing_unit" title="Graphics processing unit">Graphics processing unit</a></li>

<li><a href="Image_compression" title="Image compression">Image compression</a></li>

<li><a href="Solid_modeling" title="Solid modeling">Solid modeling</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Applied computing</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Quantum_computing" title="Quantum computing">Quantum computing</a></li>

<li><a href="E-commerce" title="E-commerce">E-commerce</a></li>

<li><a href="Enterprise_software" title="Enterprise software">Enterprise software</a></li>

<li><a href="Computational_mathematics" title="Computational mathematics">Computational mathematics</a></li>

<li><a href="Computational_physics" title="Computational physics">Computational physics</a></li>

<li><a href="Computational_chemistry" title="Computational chemistry">Computational chemistry</a></li>

<li><a href="Computational_biology" title="Computational biology">Computational biology</a></li>

<li><a href="Computational_social_science" title="Computational social science">Computational social science</a></li>

<li><a href="Computational_engineering" title="Computational engineering">Computational engineering</a></li>

<li>Differentiable computing</li>

<li><a href="Health_informatics" title="Health informatics">Computational healthcare</a></li>

<li><a href="Digital_art" title="Digital art">Digital art</a></li>

<li><a href="Electronic_publishing" title="Electronic publishing">Electronic publishing</a></li>

<li><a href="Cyberwarfare" title="Cyberwarfare">Cyberwarfare</a></li>

<li><a href="Electronic_voting" title="Electronic voting">Electronic voting</a></li>

<li><a href="Video_game" title="Video game">Video games</a></li>

<li><a href="Word_processor" title="Word processor">Word processing</a></li>

<li><a href="Operations_research" title="Operations research">Operations research</a></li>

<li><a href="Educational_technology" title="Educational technology">Educational technology</a></li>

<li><a href="Document_management_system" title="Document management system">Document management</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category</li>

<li><span class="noviewer" typeof="mw:File"><span title="Outline"></span></span> <a href="Outline_of_computer_science" title="Outline of computer science">Outline</a></li>

<li><span class="noviewer" typeof="mw:File"><span></span></span> Glossaries</li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Software_quality258" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Software_quality258" style="font-size:114%;margin:0 4em"><a href="Software_quality" title="Software quality">Software quality</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Qualities</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%;font-weight:normal;">Internal</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Maintainability#Software_engineering" title="Maintainability">Maintainability</a></li>

<li><a href="Flexibility_(engineering)" title="Flexibility (engineering)">Flexibility</a></li>

<li><a href="Software_portability" title="Software portability">Portability</a></li>

<li><a href="Reusability" title="Reusability">Reusability</a></li>

<li><a href="Computer_programming#Readability_of_source_code" title="Computer programming">Readability</a></li>

<li><a href="Scalability" title="Scalability">Scalability</a></li>

<li><a href="Software_testability" title="Software testability">Testability</a></li>

<li><a href="Understandability" class="mw-redirect" title="Understandability">Understandability</a></li>

<li><a href="Loose_coupling" title="Loose coupling">Loose coupling</a></li>

<li><a href="Orthogonality_(programming)" title="Orthogonality (programming)">Orthogonality</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%;font-weight:normal;">External</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Usability" title="Usability">Usability</a></li>

<li><a href="Reliability_engineering" title="Reliability engineering">Reliability</a></li>

<li><a href="Adaptability" title="Adaptability">Adaptability</a></li>

<li><a href="Correctness_(computer_science)" title="Correctness (computer science)">Correctness</a></li>

<li><a href="Accuracy_and_precision" title="Accuracy and precision">Accuracy</a></li>

<li><a href="Robustness_(computer_science)" title="Robustness (computer science)">Robustness</a></li>

<li><a href="Software_development_security" class="mw-redirect" title="Software development security">Security</a></li>

<li><a href="Software_system_safety" class="mw-redirect" title="Software system safety">Safety</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Standards and lists</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Non-functional_requirement#Examples" title="Non-functional requirement">Non-functional requirements</a></li>

<li><a href="List_of_system_quality_attributes" title="List of system quality attributes">List of system quality attributes</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Processes</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Software_quality_management" title="Software quality management">Software quality management</a></li>

<li><a href="Software_quality_control" title="Software quality control">Software quality control</a></li>

<li><a href="Software_quality_assurance" title="Software quality assurance">Software quality assurance</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2" style="font-weight:bold;"><div>

<li><span class="noviewer" typeof="mw:File"><span title="Commons page"></span></span> <a href="https://commons.wikimedia.org/wiki/Category:Software_quality" class="extiw external" title="commons:Category:Software quality">Commons</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox391" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Authority control databases: National </th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4013585-8">Germany</a></span></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-03" href="https://en.wikipedia.org/wiki/?title=Algorithmic_efficiency&oldid=1298631510">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>